#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<math.h>
//int main() 
//{
//	int n;
//	int m = 1;
//	scanf("%d", &n);
//	for (int j = n;j >0;j--) 
//	{
//		for (int k = j;k > 0;k--) 
//		{
//			printf("%4d", m);
//			m++;
//		}
//		printf("\n");
//	}
//	return 0;
//}




//int main() 
//{
//	int n;
//	scanf("%d", &n);
//	for (int i = 1;i<=n/2+1;i++) 
//	{
//		for (int j = 1;j <=n/2+i;j++ ) 
//		{
//			if (j < n/2-i+2)
//			{
//				printf("  ");
//			}
//			else
//				printf("* ");
//		}
//		printf("\n");
//	}
//	for (int i = n/2;i>=1;i--)
//	{
//		for (int j = 1;j <= n / 2 + i;j++)
//		{
//			if (j < n / 2 - i + 2)
//			{
//				printf("  ");
//			}
//			else
//				printf("* ");
//		}
//		printf("\n");
//	}
//	return 0;
//}



//int main()
//{
//	int n, m;
//	int sum = 0;
//	int c = 0;
//	scanf("%d %d", &n, &m);
//	for (int i = n;i <= m;i++) 
//	{
//		if (c % 5 == 0)
//			printf("\n");
//		c++;
//		printf("%5d", i);
//		sum += i;
//	}
//	printf("\n");
//	printf("%d", sum);
//	return 0;
//}



//int main() 
//{
//	int n;
//	char ch;
//	scanf("%d", &n);
//	for (int i = 1;i <= n;i++) 
//	{
//		for (int j = 1;j <= n - i;j++) 
//		{
//			printf(" ");
//		}
//		for (ch = 'A';ch <= 'A' + i - 1;ch++) 
//		{
//			printf("%c", ch);
//		}
//		for (ch = ch - 2;ch >= 'A';ch--) 
//		{
//			printf("%c", ch);
//		}
//		printf("\n");
//	}
//	return 0;
//}




//int main() 
//{
//	int n;
//	scanf("%d", &n);
//	int x, y;
//	for (x = 1;x <= 100;x++) 
//	{
//		for (y = x;y <= 100;y++) 
//		{
//			if (x * x + y * y == n) 
//			{
//				printf("%d %d\n", x, y);
//			}
//		}
//	}
//	return 0;
//}



//int main() 
//{
//	int n;
//	char m;
//	scanf("%d %c", &n, &m);
//	for (int i = 1;i <= n/2+1;i++) 
//	{
//		for (int j = 1;j <= n;j++) 
//		{
//			printf("%c", m);
//		}
//		printf("\n");
//	}
//	return 0;
//}

//
//int main() 
//{
//	int n;
//	char op = '#';
//	char se = '#';
//	int sum;
//	do 
//	{
//		scanf("%d",&n);
//		op = getchar();
//		if (se == '#')
//			sum = n;
//		else if (se == '+')
//			sum += n;
//		else if (se == '-')
//			sum -= n;
//		else
//			op = '#';
//		se = op;
//	} while (op=='+'||op=='-');
//	printf("%d", sum);
//	return 0;
//}


//int main()
//{
//	int n;
//	scanf("%d", &n);
//	for (int i = 1;i <= n / 2 + 1;i++) 
//	{
//		for (int j = 1;j <= n/2 + i ;j++) 
//		{
//			if (j <= n/2-i+1)
//				printf(" ");
//			else
//				printf("*");
//		}
//		printf("\n");
//	}
//	for (int i = n/2;i >= 1;i--)
//	{
//		for (int j = 1;j <= n / 2 + i;j++)
//		{
//			if (j <= n / 2 - i + 1)
//				printf(" ");
//			else
//				printf("*");
//		}
//		printf("\n");
//	}
//}



//int main() 
//{
//	int c;
//	double a = 2.0;
//	int b = 1;
//	int f = 1;
//	double sum = 0.0;
//	int n;
//	scanf("%d", &n);
//	for (int i = 1;i <= n;i++) 
//	{
//		sum += a / b * f;
//		c = a;
//		a = b;
//		b = c;
//		f = -f;
//	}
//	printf("%.2lf", sum);
//	return 0;
//}


//int main() 
//{
//	int x;
//	int n;
//	double sum = 1.0;
//	double m = 1.0;
//	scanf("%d %d", &n,&x);
//	for (int i = 1;i <= n;i++) 
//	{
//		m = m * i;
//		sum += pow(x, i) / m;
//	}
//	printf("%lf", sum);
//	return 0;
//}